package spreadsheet;

import java.util.Stack;
import java.text.*;

/** Class FormulaParser is used to break up and solve an expression in the form
 * of a string. It also verifies whether the expression is valid.
 * 
 * @author Cassie Wong, Audrey Paiement, Francis Bayard
 * @version 1.2 March 04, 2013
 */
public class FormulaParser {

	public static final int FIRST_COL_ASCII_CODE = 65;
	private static FormulaParser instance;
	private String regex;

	/**
	 * The SpreadSheet object from which to retrieve cell values
	 */
	private SpreadSheet spreadSheet;

	/**
	 * A stack of all cells traversed. Used to detect loops.
	 */
	private Stack<String> loopStack;

	/**
	 * 
	 * @param spreadSheet The SpreadSheet object from which to retrieve cell values
	 */
	private FormulaParser(){
		loopStack = new Stack<String>();
	}

	public static FormulaParser getInstance() {
		if( instance == null ) {
			instance = new FormulaParser();
		}

		return instance;    
	}

	public void setSpreadSheet(SpreadSheet spreadSheet) {
		this.spreadSheet = spreadSheet;
	}

	/**
	 * Parser takes an expression and breaks it down by calling various methods 
	 * that follow the order of operations.
	 * 
	 * @param str_expression		A Mathematical Equation in form of a string.
	 * @return						Returns the simplified form of the expression.
	 * @throws Exception			If the expression is non-valid, the method it calls
	 * 								will throw an exception.
	 */
	public String parse(String str_expression) throws Exception{
		int[] format = {-1};
		
		/*
		 *	check for '=' at start of expression 
		 */
		if(str_expression.charAt(0) == '=')
		{
			str_expression = str_expression.replaceAll(" ", ""); // to remove all spaces
			
			str_expression = str_expression.substring(1, str_expression.length());

			checkIfValidExpression(str_expression);
			
			str_expression = checkFormat(str_expression, format);
			
			str_expression = checkForBrackets(str_expression);

			str_expression = evaluateMulDiv(str_expression);

			str_expression = evaluateAddSub(str_expression);
			
			str_expression = String.valueOf(parseValue(str_expression));
			
			str_expression = formatValue(str_expression, format[0]);
			
			//str_expression = checkIfIntegerAndConvert(str_expression);
		}
		
		else
		{
			char currentChar;
			
			for(int i = 0; i < str_expression.length(); i++)
			{	
				currentChar = str_expression.charAt(i);
						
				if(!(Character.isLetter(currentChar) || Character.isDigit(currentChar) || currentChar == '.' ||  currentChar == ' '))
				{
					throw new Exception("Invalid character in formula: '" + currentChar + "' is invalid.");
				}
			}
		}

		return str_expression;
	}//end of parser

	/**
	 *  
	 */
	private String formatValue(String expression, int theFormat)
	{
		switch(theFormat)
		{
			case 0:
				DecimalFormat df = new DecimalFormat("#,###,###,###,###,###,###.00");
				expression = df.format(Double.parseDouble(expression));
				expression = "$" + expression;
				break;
				
			case 1:
				expression = String.format("%e", Double.parseDouble(expression));
				break;
			
			case 2: 
				DecimalFormat intf = new DecimalFormat("#");
				expression = intf.format(Double.parseDouble(expression));
				break;
				
			default:
				break;
		}
		
		return expression;
	}
	
	
	/**
	 *	checkFormat check to see which format i being used 
	 * 
	 *  @param expression  String expression to be changed to specified format
	 *  @param theFormat   Integer which represents the format
	 *  				   -1 - no format
	 * 				  		1 - monetary
	 * 				  		2 - scientific
	 * 				  		3 - integer
	 * 
	 * 	@return int  format
	 */
	private String checkFormat(String expression, int[] theFormat) throws Exception
	{
		char lastChar = expression.charAt(expression.length() - 1);
		char secondLastChar = expression.charAt(expression.length() - 2); 
		
		if(secondLastChar == ':')
		{
			switch(lastChar)
			{
				case 'M':
				case 'm':
					theFormat[0] = 0;
					break;
					
				case 'S':
				case 's':
					theFormat[0] = 1;
					break;
					
				case 'I':
				case 'i':
					theFormat[0] = 2;
					break;
					
				default:
					throw new Exception("Error: require format after ':'. Format can be 'M', 'S', 'I'.");
			}
			
			if(theFormat[0] != -1)
			{
				return expression.substring(0, (expression.length()-2));
			}
		}
				
		return expression;
	}
	
	
	/**
	 * 	checkIfIntegerAndConvert check to see if a given string represents
	 * 	an integer and removes decimal places if it is.	 
	 * 
	 * 	@param expression	String of the expression to be checked
	 *  @return expression	returns a String of an appropriate int or double 
	 */
	private String checkIfIntegerAndConvert(String expression)
	{
		int decimalAt = 0;
		boolean isInteger = true;

		//check for a decimal point
		for(int i = 0; i < expression.length(); i++)
		{
			if(expression.charAt(i) == '.')
			{
				decimalAt = i;
				break;
			}
		}

		//check if there are non zero numbers after decimal point,
		//if no non-zero numbers are found, then the string represents
		//an integer
		if(decimalAt > 0)
		{	
			for(int i = (decimalAt+1); i < expression.length(); i++)
			{
				if(expression.charAt(i) != '0')
				{
					isInteger = false;
					break;
				}
			}

			if(isInteger)
			{
				expression = expression.substring(0, decimalAt);
			}
		}

		return expression;
	}

	/**
	 * 	checkForInvalidCharacters will verify if there are 
	 * 	any characters that would make the formula invalid.
	 * 	
	 * 	@param expression	A Mathematical Equation in form of a string
	 *  @throws Exception	If any character is not a valid character
	 */
	private void checkIfValidExpression(String expression) throws Exception{
		char currentChar;
		char nextChar;
		
		if(expression.length() == 0)
		{
			throw new Exception("No value entered in cell");
		}
		
		currentChar = expression.charAt(expression.length() - 1);
		
		if(currentChar == ':' || isOperator(currentChar))
		{
			throw new Exception("Incomplete statement: '" + currentChar + "' at the end.");
		}
		
		//loop through expression to check if expression is valid
		for(int i = 0; i < expression.length(); i++)
		{
			currentChar = expression.charAt(i);

			//if is not a digit, a letter, '+', '-', '/', '*', '.', ':', '(', or ')' throw an exception
			if(!isValidChar(currentChar))
			{
				throw new Exception("Entered invalid character: '" + currentChar + "' is an invalid character.");
			}
			
			if(i < (expression.length() - 1))
			{
				if(currentChar == '.')
				{	
					if(i == 0)
					{
						throw new Exception("Invalid use of period '.'. Expression cannot start with period.");
					}
					
					else if(!Character.isDigit(expression.charAt(i-1)))
					{
						throw new Exception("Invalid use of period '.'. Must have digit before period.");
					}
					
					else if(!Character.isDigit(expression.charAt(i+1)))
					{
						throw new Exception("Invalid use of period '.'. Must have digit after period.");
					}
				}
				
				nextChar = expression.charAt(i+1);
				
				if(currentChar == ':')
				{
					if(i != expression.length() - 2)
					{
						throw new Exception("Invalid expression: ':' is in invalid location.");
					}
					
					else if(expression.length() < 3)
					{
						throw new Exception("Error: Cannot format current expression.");
					}
				}
				
				if(isOperator(currentChar) && nextChar == '-')
				{
					if((i + 2) >= expression.length() || !Character.isDigit(expression.charAt(i+2)))
					{
						throw new Exception("Invalid expression: \"--\"");
					}
				}
				
				else if(isOperator(currentChar))
				{
					if(isOperator(nextChar))
					{
						throw new Exception("Entered two consecutive operators: \"" + currentChar + "\" is invalid.");
					}
				}
			}
		}
	}

	/**
	 *  isOperator checks to see if a given character is an
	 *  operator
	 *  
	 *  @param c	character to be evaluated
	 *  @return 	true if character is an operator, false otherwise
	 */
	private boolean isOperator(char c)
	{
		//if character is an operator, return true
		if(c == '+' || c == '-' || c == '/' || c == '*')
		{
			return true;
		}

		else
		{
			return false;
		}
	}

	/**
	 *  isOperator checks to see if a given character is an
	 *  operator
	 *  
	 *  @param c	character to be evaluated
	 *  @return 	true if character is a valid character, false otherwise
	 */
	private boolean isValidChar(char c)
	{
		//if character is an operator, return true
		if((Character.isLetter(c) && Character.isUpperCase(c)) || Character.isDigit(c) || isOperator(c) || c == '.' || c == '(' || c == ')' || c == ':')
		{
			return true;
		}

		else
		{
			return false;
		}
	}

	/**
	 * 	checkForBrackets will search the string for "(" and ")" 
	 * 	it will pass the expression inside the outer-most brackets into parser to simply
	 * 	In addition, it verifies that there are matching open and closed brackets.
	 * @param str_expression		A Mathematical Equation in form of a string	
	 * @return						Simplified version of the expression
	 * @throws Exception			If the amount of open and closed brackets do not match
	 */
	public String checkForBrackets(String str_expression)throws Exception{
		int begin = 0; //to keep track of the index of the first open bracket
		int end = 0; //to keep track of the index of the last closed brackets
		
		Stack<Integer> tracker = new Stack<Integer>(); //stack to verify whether the number of open brackets will match the closed ones.
		String simplified_expr = new String(); //to store simplified expression.
		String new_expression = new String(str_expression);

		for (int i = 0; i < str_expression.length();i++){
			if(str_expression.charAt(i) == '('){
				if(tracker.empty())
					begin = i; //If the stack is empty, then this is the first open bracket.
				tracker.push(1);
			}//end of if '('
			
			if(str_expression.charAt(i) == ')'){
				if (tracker.empty()) throw new Exception("Mismatched brackets: you have too many \")\"");
				tracker.pop();
				end = i;
				if (tracker.empty()){
					//System.out.println(str_expression.substring(begin, end+1));
					simplified_expr = new String(parse("=" + str_expression.substring(begin+1, end)));
					new_expression = new_expression.replace(str_expression.substring(begin, end+1), simplified_expr);
				}
			}//end of if ')'
		}//end of for

		if(!tracker.empty()) throw new Exception("Mismatched brackets: you have too many \"(\"");
		return new_expression;
	}// end of checkForBrackets


	/**
	 * Separates values and operators, placing them into stacks.
	 * Evaluates for multiplication and division by calling appropriate method.
	 * @param str_expression		A Mathematical Equation in form of a string.
	 * @return						Returns the simplified form of the expression.
	 * @throws Exception			If the expression is non-valid, the method it calls
	 * 								will throw an exception.
	 */
	private String evaluateMulDiv(String str_expression) throws Exception{
		Stack<String> values = new Stack<String>();
		Stack<String> operators = new Stack<String>();
		String expression_copy = new String(str_expression);
		
		for (int j = str_expression.length() - 1; j >= 0; j--){
			char temp= str_expression.charAt(j);
		
			if(temp == '-'){ //check if it's a subtraction sign or a negative.
				if(j == 0) break; //If the negative is the first character, break out of the if statement
				// so that we will not receive a "String index out of range: -1" for the condition below
				
				if(isNumeric(str_expression.substring(j-1, j))){
					operators.push("-");
					values.push(expression_copy.substring(j+1));
					expression_copy = expression_copy.substring(0, j);
				} 
			} 
			
			else if(temp == '+' ||temp == '*' ||temp == '/' ){
				operators.push(str_expression.substring(j, j+1));
				values.push(expression_copy.substring(j+1));
				expression_copy = expression_copy.substring(0, j);	
			} 
		}
		
		values.push(expression_copy);// to get the last value.

		String op, v1, v2, result; //operator, value1, value2 and result of calculation.
		String new_expression = new String();
		
		while(!operators.empty()){
			op = operators.pop();
			
			if(op.equals("*")){
				v1 = values.pop();
				v2 = values.pop();
				result = multiply(v1, v2);
				values.push(result);
			} 
			
			else if (op.equals("/")){
				v1 = values.pop();
				v2 = values.pop();
				result = divide(v1, v2);
				values.push(result);
			} 
			
			else {
				v1 = values.pop();
				new_expression = new_expression.concat(v1).concat(op);
			}
		}
		
		new_expression = new_expression.concat(values.pop());
		
		if(!values.empty()) System.out.println("Problem with evaluateMulDiv");

		return new_expression;
	}//end of evaluateMulDiv


	/**
	 * Separates values and operators
	 * Evaluates additions and subtractions by calling appropriate methods
	 * 
	 * @param str_expression		A Mathematical Equation in form of a string.
	 * @return						Returns the simplified form of the expression.
	 * @throws Exception			If the expression is non-valid, the method it calls
	 * 								will throw an exception.
	 */
	private String evaluateAddSub(String str_expression) throws Exception{
		Stack<String> values = new Stack<String>();
		Stack<String> operators = new Stack<String>();
		String expression_copy = new String(str_expression);
		
		for (int j = str_expression.length() - 1; j >= 0; j--){
			char temp = str_expression.charAt(j);
			
			if(temp == '-'){ //check if it's a subtraction sign or a negative.
				if(j == 0) break; //If the negative is the first character, break out of the if statement
				// so that we will not receive a "String index out of range: -1" for the condition below
				if(isNumeric(str_expression.substring(j-1, j))){
					operators.push("-");
					values.push(expression_copy.substring(j+1));
					expression_copy = expression_copy.substring(0, j);
				} 
			} 
			
			else if(temp == '+'){
				operators.push("+");
				values.push(expression_copy.substring(j+1));
				expression_copy = expression_copy.substring(0, j);	
			} 
		}
		
		values.push(expression_copy);// to get the last value.

		String op, v1, v2, result; //operator, value1, value2 and result of calculation.
		
		while(!operators.empty()){
			op = operators.pop();
			
			if(op.equals("+")){
				v1 = values.pop();
				v2 = values.pop();
				result = add(v1, v2);
				values.push(result);
			} else if (op.equals("-")){
				v1 = values.pop();
				v2 = values.pop();
				result = subtract(v1, v2);
				values.push(result);
			} else {
				System.out.println("Problem with evaluateAddSub");
			}
		}

		return values.pop();
	}//end of evaluateAddSub

	/**
	 * Multiplies 2 values together. (Argument 1 x Argument 2)
	 * @param value1		Argument 1 for equation.
	 * @param value2		Argument 2 for equation.
	 * @return				Returns the result of the multiplication, in form of a string.
	 * @throws Exception	If Error occurs while parsing.
	 */
	private String multiply(String value1, String value2)throws Exception{
		double num1 = parseValue(value1);
		double num2 = parseValue(value2);
		double dResult = num1 * num2;
		
		if( dResult == ( int )dResult ) {
			return Integer.toString( ( int )dResult );
		}
		return Double.toString( dResult );
	}//end of multiply


	/**
	 * Divides 2 values together. (Argument 1 / Argument 2)
	 * @param value1		Argument 1 for equation.
	 * @param value2		Argument 2 for equation.
	 * @return				Returns the result of the division, in form of a string.
	 * @throws Exception	If Division by 0.
	 */
	private String divide(String value1, String value2)throws Exception{
		double num1 = parseValue(value1);
		double num2 = parseValue(value2);

		if(num2 == 0) {
			throw new Exception("Division By Zero");
		}
		double dResult = num1 / num2;
		if( dResult == ( int )dResult ) {
			return Integer.toString( ( int )dResult );
		}
		return Double.toString( dResult );
	}//end of divide

	/**
	 * Adds 2 values together. (Argument 1 + Argument 2)
	 * @param value1		Argument 1 for equation.
	 * @param value2		Argument 2 for equation.
	 * @return				Returns the result of the addition, in form of a string.
	 * @throws Exception	If Error occurs while parsing.
	 */
	private String add(String value1, String value2) throws Exception{
		double num1 = parseValue(value1);
		double num2 = parseValue(value2);

		double dResult = num1 + num2;
		if( dResult == ( int )dResult ) {
			return Integer.toString( ( int )dResult );
		}
		return Double.toString( dResult );
	}//end of add

	/**
	 * Subtracts 2 values together. (Argument 1 - Argument 2)
	 * @param value1		Argument 1 for equation.
	 * @param value2		Argument 2 for equation.
	 * @return				Returns the result of the subtraction, in form of a string.
	 * @throws Exception	If Error occurs while parsing.
	 */
	private String subtract(String value1, String value2) throws Exception{
		double num1 = parseValue(value1);
		double num2 = parseValue(value2);

		double dResult = num1 - num2;
		if( dResult == ( int )dResult ) {
			return Integer.toString( ( int )dResult );
		}
		return Double.toString( dResult );
	}//end of subtract

	/**
	 * If the string is numeric, it'll convert the string to a double
	 * If the string is a cell, it returns the value of that cell
	 * @param value			A value in form of a string.
	 * @return				The value in form of a double.
	 * @throws Exception	If the string is neither numeric nor a cell, it is an invalid argument.
	 */
	private double parseValue(String value)throws Exception{
		double num = 0;
		if(isNumeric(value)){
			num = Double.parseDouble(value);
		} 
		
		else if(isCell(value)){
			if (loopStack.contains(value.toUpperCase())) //Check if the cell name is already in the stack
			{
				loopStack.clear();
				
				throw new Exception("Circular cell reference.");
			}
			
			loopStack.push(value.toUpperCase());
			
			num = getCellValue(value);
			
			loopStack.pop();
		} 
		
		else{
			throw new Exception("Invalid Argument");
		}

		return num;
	}//end of parseValue

	/**
	 * Verifies whether a given string is numerical (in form of a double)
	 * @param str		A string that needs to be checked.
	 * @return			Returns true if the string is numeric, else returns false.
	 */
	private boolean isNumeric(String str){
		return str.matches("-?\\d+(\\.\\d+)?");  //match a number with optional '-' and decimal.
	}//end of isNumeric


	/**
	 * Verifies whether a given string is referring to a cell.
	 * @param str		A string that needs to be checked.
	 * @return			Returns true if the string is the name of a cell, else returns false.
	 */
	private boolean isCell(String str){
		formulaStr();
		return str.matches(regex);
	}//end of isCell
	
	private String formulaStr()
	{
		int row = spreadSheet.NUMBER_OF_ROWS;
		int col = spreadSheet.NUMBER_OF_COLUMNS - 1;
		regex = "^(([A";
		
		// column section
		if (col <= 26)
		{
			regex += "-";
			regex += (char) (col+64);
		}
		else if (col <= 52)
		{
			regex += "-Z])|([A][A";
			if (col != 27)
			{
				regex += "-";
				regex += (char) (col+38);
			}
		}
		else
		{
			regex += "-";
			regex += (char) (((col-1)/26)+63);
			regex += "][A-Z])|([";
			regex += (char) (((col-1)/26)+64);
			regex += "][A";
			if ((col % 26) != 1)
			{
				regex += "-";
				if ((col % 26) == 0) regex += "Z";
				else regex += (char) (col % 26);
			}
		}
		regex += "]))";
		
		// row section
		regex += "(([1-9])|([1";
		
		if (row < 100)
		{
			regex += "-";
			regex += (row / 10) - 1;
			regex += "][0-9])|([";
			regex += row / 10;
			regex += "][0";
			if ((row % 10) != 0)
			{
				regex += "-";
				regex += row % 10;
			}
		}
		else if (row < 110)
		{
			regex += "-9][0-9])|([1][0][0";
			if (row != 100)
			{
				regex += "-";
				regex += row % 10;
			}
		}
		else if (row < 120)
		{
			regex += "-9][0-9])|([1][0][0-9])|([1][1][0";
			if (row != 110)
			{
				regex += "-";
				regex += row % 10;
			}
		}
		else if (row < 200)
		{
			regex += "-9][0-9])|([1][0-";
			regex += ((row / 10) % 10) - 1;
			regex += "][0-9])|([1][";
			regex += (row / 10) % 10;
			regex += "][0";
			if ((row % 10) != 0)
			{
				regex += "-";
				regex += row % 10;
			}
		}
		else if (row < 210)
		{
			regex += "-9][0-9])|([1][0-9][0-9])|([2][0][0";
			if (row != 200)
			{
				regex += "-";
				regex += row % 10;
			}
		}
		else if (row < 220)
		{
			regex += "-9][0-9])|([1][0-9][0-9])|([2][0][0-9])|([2][1][0";
			if (row != 210)
			{
				regex += "-";
				regex += row % 10;
			}
		}
		else if (row < 300)
		{
			regex += "-9][0-9])|([1][0-9][0-9])|([2][0";
			regex += ((row / 10) % 10) - 1;
			regex += "][0-9])|([2][";
			regex += (row / 10) % 10;
			regex += "][0";
			if ((row % 10) != 0)
			{
				regex += "-";
				regex += row % 10;
			}
		}
		else if (row < 1000)
		{
			regex += "-9][0-9])|([1-";
			regex += (row / 100) - 1;
			regex += "][0-9][0-9])|([";
			regex += row / 100;
			regex += "][0";
			if (((row / 10) % 10) != 0)
			{
				regex += "-";
				regex += ((row / 10) % 10) - 1;
				regex += "][0-9])|([";
				regex += row / 100;
				regex += "][";
				regex += ((row / 10) % 10);
			}
			regex += "][0";
			if ((row % 10) != 0)
			{
				regex += "-";
				regex += row % 10;
			}
		}
		else regex += "-9][0-9])|([1-9][0-9][0-9])|([1][0][0][0";
		regex += "]))$";
		
		return regex;
	}


	/**
	 * Gets a cell's value from its name. 
	 * @param cellName
	 * @return Returns the cell's value as a double
	 * @throws Exception If the cell's formula cannot be parsed.
	 * @throws NumberFormatException If the cell's value cannot be parsed as a double.
	 */
	private double getCellValue(String cellName) throws NumberFormatException, Exception {
		int i;
		int j;
		
		if (cellName.toUpperCase().charAt(1) >= FIRST_COL_ASCII_CODE)
		{
			i = Integer.parseInt(cellName.substring(2)) - 1;
			j = (cellName.toUpperCase().charAt(0) - FIRST_COL_ASCII_CODE + 1) * 26;
			j += cellName.toUpperCase().charAt(1) - FIRST_COL_ASCII_CODE + 1;
		}
		else
		{
			i = Integer.parseInt(cellName.substring(1)) - 1;
			j = cellName.toUpperCase().charAt(0) - FIRST_COL_ASCII_CODE + 1;
		}

		SpreadSheetCell cell = spreadSheet.getCells()[i][j];

		if (cell.getCellType().equals(SpreadSheetCell.CELL_TYPES_FORMULA))
			return Double.parseDouble(parse(cell.getCellValue()));
		else
			return Double.parseDouble(cell.getCellValue());

	}//end of getCellValue
}
